'''
LRU缓存：
使用hash快速查找，使用双链来找到最近使用和最少使用的对象。（表头和表尾）
get时刷新对象的位置为最新。
put时也更新，如果超出最大阈值，则把末尾的作为lru删除。
'''
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 哈希表
        self.head = Node(0, 0)  # 双向链表的头部
        self.tail = Node(0, 0)  # 双向链表的尾部
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add(node)
        if len(self.cache) > self.capacity:
            lru = self._pop()
            del self.cache[lru.key]

    def _add(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove(self, node: Node) -> None:
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

    def _pop(self) -> Node:
        lru = self.tail.prev
        self._remove(lru)
        return lru

# 测试代码
lru_cache = LRUCache(2)
lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1))  # 返回 1
lru_cache.put(3, 3)      # 淘汰键2
print(lru_cache.get(2))  # 返回 -1 (未找到)
lru_cache.put(4, 4)      # 淘汰键1
print(lru_cache.get(1))  # 返回 -1 (未找到)
print(lru_cache.get(3))  # 返回 3
print(lru_cache.get(4))  # 返回 4
